mathematische Programmierung

I

mathematische Programmierung,

 

Optimierung.

II

mathematische Programmierung

 

[von englisch programming, »planen«], mathematische Optimierung, auch mathematische Planungsrechnung, Operations-Research: Sammelbegriff für solche Modelle, die aus einer Zielfunktion und einem System von Nebenbedingungen (Gleichungen und Ungleichungen) mit Variablen beliebiger Potenz und Verknüpfung bestehen, sowie für Lösungsverfahren, die der Ermittlung der Werte dieser Unbekannten dienen.

 

Sind Zielfunktion und Nebenbedingungen eines Modells der mathematischen Programmierung linear, spricht man von linearer Programmierung (linearer Optimierung). In der Standardform hat ein Modell der linearen Programmierung (LP-Modell) folgendes Aussehen:

 

Zielfunktion:

 

Nebenbedingungen:

 

 

mit a_ij, b_i und c_j als Konstanten sowie x_j als Variablen. Für die Bestimmung derjenigen Werte der x_j, die die Zielfunktion maximieren, können das von G. B. Dantzig entwickelte Simplexverfahren oder eine Reihe davon abgeleiteter Verfahrensversionen eingesetzt werden. Dies sind numerischen Verfahren, die iterativ in einer endlichen Zahl von Schritten die optimalen Werte für x_j liefern. Sie sind auch anwendbar, wenn die Zielfunktion zu minimieren ist und/oder Größer-gleich-Relationen beziehungsweise Ist-gleich-Relationen in den Nebenbedingungen gelten.

 

Eine Sondersituation liegt vor, wenn für ein Modell, das im Aussehen einem LP-Modell gleicht, Lösungswerte für einige oder alle Variablen x_j gefordert werden, die ganzzahlig sind. Solche Modelle und entsprechende Lösungsverfahren werden dem Gebiet der ganzzahligen Programmierung (ganzzahlige Optimierung) zugerechnet. Hier ist der Lösungsvorgang zweistufig. Er beginnt mit dem Einsatz eines Lösungsverfahrens der linearen Programmierung, das unter Umständen bereits ganzzahlige Lösungswerte für die betreffenden x_j liefert (natürliche Ganzzahligkeit der optimalen x_j). Anderenfalls wird, ausgehend von der erhaltenen nichtganzzahligen (d. h. unzulässigen) Lösung, der Einsatz spezieller Lösungsverfahren erforderlich. Bewährt haben sich dabei insbesondere die zu den Entscheidungsbaumverfahren gehörenden Branch-and-bound-Verfahren. - Die lineare und die ganzzahlige Programmierung werden in der betrieblichen Praxis häufig für die optimale Lösung von Problemen der Produktionsprogramm-, Transport-, Finanz- und Personaleinsatzplanung verwendet, insbesondere, da entsprechende benutzerfreundliche Software in großer Vielfalt für Computer aller Größenklassen verfügbar ist. So können im Bereich der linearen Programmierung Modelle mit bis zu einigen Mio. Nebenbedingungen und ebenso vielen Variablen verarbeitet werden, im Bereich der ganzzahligen Programmierung in der Regel Modelle mit einigen 100 Nebenbedingungen und Variablen (beziehungsweise einer größeren Anzahl, wenn man auf Näherungslösungen zurückgreift).

 

Sind die Zielfunktion und das zugehörige System von Nebenbedingungen eines Modells der mathematischen Programmierung nichtlinear, spricht man auch von nichtlinearer Programmierung (nichtlinearer Optimierung). Praktische Bedeutung hat die nichtlineare Programmierung insbesondere bei der Optimierung chemischer Prozesse. Die verfügbaren Lösungsverfahren sind weniger leistungsfähig als die der linearen Programmierung.

 

Literatur:

 

K. Neumann u. M. Morlock: Operations Research (Neuausg. 1993);

 Manfred Meyer u. K. Hansen: Planungsverfahren des Operations-Research (⁴1996);

 G. B. Dantzig u. M. N. Thapa: Linear programming, auf mehrer Bde. ber. (New York 1997 ff.).